//
// Created by mac on 2023/12/4.
//

// 有效的括号
class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> st;
        for(const auto ch : s)
        {
            if(ch == '(' || ch == '[' || ch == '{') st.push(ch);
            else
            {
                // 1、右括号多
                if(st.empty()) return false;

                char top = st.top();
                if(top == '(' && ch == ')' || top == '[' && ch == ']' || top == '{' && ch == '}')
                    st.pop();
                else
                    return false; // 2、括号不匹配
            }
        }

        return st.empty(); // 3、最后若栈为空，说明左括号全部正确匹配完成
    }
};

// 用栈实现队列
class MyQueue
{
private:
    stack<int> st1, st2;

public:
    // 构造函数，什么都不需要做
    MyQueue()
    {}

    // 入队列
    void push(int x)
    {
        st1.push(x);
    }

    // 出队列
    int pop()
    {
        // 队列为空，则返回-1
        if(st1.empty() && st2.empty()) return -1;
        // 若 st2 为空，则需要从 st1 中把元素更新过来
        if(st2.empty())
        {
            while(!st1.empty())
            {
                st2.push(st1.top());
                st1.pop();
            }
        }
        //  st2 栈顶元素即使队列的对首元素，删除即可
        int ans = st2.top();
        st2.pop();
        return ans;
    }

    int peek()
    {
        // 队列为空，则返回-1
        if(st1.empty() && st2.empty()) return -1;
        // 若 st2 为空，则需要从 st1 中把元素更新过来
        if(st2.empty())
        {
            while(!st1.empty())
            {
                st2.push(st1.top());
                st1.pop();
            }
        }
        //  st2 栈顶元素即使队列的对首元素，返回即可
        return st2.top();
    }

    // 队列判空
    bool empty()
    {
        return st1.empty() && st2.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

// 最小栈
class MinStack
{
private:
    stack<int> st;   //存放栈元素
    stack<int> minSt;//存放st中，最小元素序列

public:
    // 默认构造函数
    MinStack()
    {}

    // 栈中插入元素
    void push(int val)
    {
        // 先把元素入栈
        st.push(val);
        // 1、若最小栈为空（说明是第一个插入元素），此时 val 直接入最小栈
        // 2、若最小栈不为空，则比较最小栈栈顶元素，再决定是否插入最小栈
        if(minSt.empty()) minSt.push(val);
        else
        {
            if(val <= minSt.top()) minSt.push(val);
        }
    }

    // 弹出栈顶元素
    void pop()
    {
        // 若栈顶元素为栈中最小元素，则需要同步更新最小栈
        if(st.top() == minSt.top()) minSt.pop();
        // 弹出栈顶元素
        st.pop();
    }

    // 获取栈顶元素
    int top()
    {
        return st.top();
    }

    // 获取栈中最小元素
    int getMin()
    {
        return minSt.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */